package sliding_window;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.TimeUnit;

/**
 *  串联所有单词的子串
 *  困难题！！！
 */

public class Demo20250321 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        // 保存 words 中所有单词的频次
        Map<String, Integer> hash1 = new HashMap<>();
        for (String str : words) {
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }
        int len = words[0].length();
        int m = words.length;
        // 执行次数
        for (int i = 0; i < len; i++) {
            // 保存窗口内所有单词的频次
            Map<String, Integer> hash2 = new HashMap<>();
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                // 进窗口， 维护 count
                // substring 主要用于从一个字符串中提取子字符串
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                // 不能用 get()，要用 getOrDefault(in, 0)
                // 如果用 get 第一次比较如果 hash1 中没有in的话会报错
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                // 判断
                if (right - left + 1 > len * m) {
                    // 出窗口，维护 count
                    String out = s.substring(left, left + len);
                    // 不能用 get()，要用 getOrDefault(in, 0)
                    // 如果用 get 第一次比较如果 hash1 中没有in的话会报错
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                // 更新结果
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}
